package Demo02;

public class Main {
    
}

class Solution {
    public static void main(String[] args) {
        int[][] arr = {
                {1,3,1},
                {1,5,1},
                {4,2,1}
        };
        System.out.println(minPathSum(arr));
    }
    public static int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid.length;
        int[][] dis = new int[n][m];
        dis[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            dis[i][0] = dis[i-1][0] + grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            dis[0][i] = dis[0][i-1] + grid[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dis[i][j] = grid[i][j] + Math.min(dis[i - 1][j], dis[i][j - 1]);
            }
        }
        return dis[n-1][m-1];
    }
}